import java.util.Scanner;

/**
 * Created by L.jp
 * Description:
 * 星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：n对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。
 * |1 1|^n => |Xn ..|
 * |1 0|      |.. ..|
 *
 * 例如n=2时，
 * |1 1|^2 => |1 1| * |1 1| => |2 1|
 * |1 0|      |1 0|   |1 0|    |1 1|
 * 即2对应的数是“0002”。
 *
 * 输入描述:
 * 输入有多组数据。
 * 每组数据两行：第一行包含一个整数n (1≤n≤100)；第二行包含n个正整数Xi (1≤Xi≤10000)
 *
 *
 * 输出描述:
 * 对应每一组输入，输出一行相应的密码。
 * 示例1
 * 输入
 * 6
 * 18 15 21 13 25 27
 * 5
 * 1 10 100 1000 10000
 * 输出
 * 418109877711037713937811
 * 00010089410135017501
 * User: 86189
 * Date: 2022-03-22
 * Time: 18:35
 */
/*  根据分析得出，矩阵是固定的：| 1  1|      当n=1是，星际密码就是这个矩阵的一次方的左上角的数值就是0001
                           | 1  0|      当n=2时，星际密码就是这个矩阵的二次方的左上角的值就是0002
                                        当n=3时，星际密码就是这个矩阵的三次方的左上角的值就是0003
                                        当n=4时，星际密码就是这个矩阵的四次方的左上角的值就是0005
                                        当n=5时，星际密码就是这个矩阵的五次方的左上角的值就是0008
                                        。。。。。说明矩阵n次方的左上角的值是符合斐波那契数列的规律的

         对输入样例进行分析得知，输入的n代表有矩阵次方的种数，而第二行的n个数，就是代表这个固定矩阵的次方
         对于输出，他不是一个整数，更像是一串字符串，每四个数代表这个固定矩阵n次方的左上角的值，输出结果把每一个矩阵的n次方的结果都串在了一起
         所以先对矩阵每一个n次方的左上角的值进行存储，然后在输出时利用字符串拼接函数，拼接他们

*
* */
public class Main {
    public static void main(String[] args) {
        //对于斐波那契的题目，我们有必要先把每一项的斐波那契的数值存储起来
        long[] fb=new long[10001];
        //由于当n==2时，密码就是2了，但是正常的斐波那契数第三个数才是2，所以我们直接从第二项开始，n==1就代表斐波那契第二项
        fb[1]=1;
        fb[2]=2;
        for(int i = 3;i<10001;i++){
            fb[i]=fb[i-1]+fb[i-2];
            //对结果只取后四位
            fb[i]%=10000;
        }
        //输入
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            //循环输入n个数，代表矩阵的每一个n次方
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < n; i++){
                int num=scanner.nextInt();
                //对于输入的每一个n，我们都可以在输入时直接输出矩阵n次方的密码
                //需要利用字符串拼接函数，一直拼接,这个拼接是有格式的，以%04d的格式拼接
                sb.append(String.format("%04d",fb[num]));  //内置了toString方法，所以可以使用StringBuilder拼接
            }
            System.out.println(sb); //返回最终拼接的结果
        }
    }
}
